1. Field of the Invention
The present invention relates generally to optimizing the use of dynamically-shared programs and libraries, and more particularly to a system and method for removing indirect addressing from a main executable (program) that accesses shared programs and libraries by utilizing cross-module optimization to collect information concerning symbol definitions and uses.
2. Related Art
In modern software development, modular design and structured programming are essential for making programs manageable. A key method for the structured organization of programs is the separation of program code into multiple source files, called modules or compilation units. Storing program code in different files facilitates the accessing, editing, sharing and maintenance of these source files. It also eases compilation overhead because only affected modules need to be re-compiled when code is changed. Separate compilation is desirable when several programmers work on the same program and mandatory when different parts of a program are written in different languages. It is the function of a linker/loader to identify and resolve external references and common symbols when the program is finally loaded for execution.
FIG. 1 illustrates the flow of a traditional compiler. Front end(s) 110 supports may different programming languages (e.g., C, Pascal, FORTRAN, ADA, PL/1, COBOL, etc.). In fact, front end 110 may include multiple sources of user code. Front end 110 produces Ucode object 115 (also referred to as intermediate code). Ucode object 115 is optimized by Ucode optimizer 120. Ucode optimizer 120 performs common global optimizations and register allocation on intermediate code to produce an optimized ucode object 125. Code Generator 130 performs local optimization and translates optimized Ucode object 125 to assembly language and symbol table 135. Assembler 140 performs peep-hole optimizations and pipeline scheduling to produce a machine language object file 145. Machine code objects can be stored in libraries 160 or linked directly into a final executable 155 by link editor 150. This process is performed for each separate module of source code.
Separate modules help programmers, but create problems for the optimizing compiler. Optimizers perform best when all of the information regarding a piece of code is available. Under separate compilation, the optimizers do not have complete information because interacting parts of the code exist in separate files. As a result of this problem, techniques to optimize across module and language barriers have been developed (e.g., the MIPS Ucode compiler which compiles code running on the MIPS R3000 processor or other processors within the MIPS family of processors).
It is becoming increasingly common to dynamically-link shared libraries. In general, dynamically-linked programs do not perform as well as statically-linked programs. Statically-linked programs do not by definition change at run-time, whereas dynamically-linked programs may change because of shared libraries and the like. Many UNIX based systems support dynamic linking of shared libraries because they provide many desirable features (See MIPS Processor Supplement for the System V Application Binary Interface, Prentice Hall, Englewood Cliffs, N.J. (1990); Arnold, J. Q., "Shared Libraries on UNIX System V," Proc. Summer Usenix, pp. 1-10 (1986); Auslander, IBM Journal of Research and Development 34(1):98-104 (1990); Coutant and Ruscetta, "Shared Libraries for HP-UX," Hewlett-Packard Journal, pp. 46-53 (June 1992); Gingell et al., "Shared Libraries in SunOS," Proc. Summer Usenix, pp. 131-145 (Summer 1987)). For example, both disk space and physical memory utilization are reduced due to increased sharing, and shared libraries can be replaced transparently without re-linking all user programs. More in-depth discussions can be found in Gingell, Unix Review 7(8):56-66 (1989); Sabatella, "Issues in Shared Libraries Design," Proc. Summer Usenix, pp. 11-23 (June 1990). However, the use of dynamic shared libraries does incur a performance penalty. Dynamically-linked programs generally run slower than statically-linked programs because they incur extra run-time overhead. This overhead includes (1) the execution of extra instructions resulted from indirect addressing and run-time symbol resolutions, and (2) extra memory requirement due to poor locality of functions in shared libraries and data structures used by the run-time linker. The present invention is related to overcoming the problem associated with indirect addressing.
Several optimizations have been proposed to improve the performance of shared libraries. For example, run-time overhead in indirect function calls can be improved by reducing the number of instructions used in the calling sequence (see Keppel and Russell, "Faster Dynamic Linking for SPARC V8 and System V.4," Technical Report Dec. 08, 1993, University of Washington (1993)). Symbol resolutions can be deferred and carried out on-demand to improve start-up time (see Sabatella, "Issues in Shared Libraries Design," Proc. Summer Usenix, pp. 11-23 (June 1990)). Loading and fixing-up of shared libraries can be cached to reduce the amount of work for subsequent invocations (see Nelson and Hamilton, "Higher Performance Dynamic Linking Through Caching," Proc. Summer Usenix, pp. 253-266 (June 1993); Orr et al., "Fast and Flexible Shared Libraries," Proc. Summer Usenix, pp. 237-251 (June 1993)). These methods are effective in speeding up the execution of dynamically-linked programs from their corresponding initial implementations. However, there still remains significant performance degradation of these programs when compared with their statically-linked counterparts.